package org.lql.algo.codecrush.week007;

import java.util.ArrayList;
import java.util.List;

/**
 * @author: liangqinglong
 * @date: 2025-08-18 13:55
 * @description: 658. 找到 K 个最接近的元素 <a href="https://leetcode.cn/problems/find-k-closest-elements/description/">...</a>
 **/
public class FindClosestElements {

	public List<Integer> findClosestElements(int[] arr, int k, int x) {
		int n = arr.length;
		int left = 0, right = n - k;
		while (left < right) {
			int mid = (left + right) >>> 1;
			// 比较窗口 [mid, mid+k-1] 与 [mid+1, mid+k] 哪个更好
			if (x - arr[mid] > arr[mid + k] - x) {
				left = mid + 1;   // 右边更近
			} else {
				right = mid;      // 左边不差（含相等时偏左，满足 a<b 的并列规则）
			}
		}
		List<Integer> res = new ArrayList<>(k);
		for (int i = left; i < left + k; i++) {
			res.add(arr[i]);
		}
		return res; // 已经是升序
	}

	public static void main(String[] args) {
		FindClosestElements fce = new FindClosestElements();
		System.out.println(fce.findClosestElements(new int[]{1, 2, 3, 4, 5}, 4, 3));
		System.out.println(fce.findClosestElements(new int[]{1, 1, 2, 3, 4, 5}, 4, -1));
	}

}

